package algotithm.weekendrace.春季赛.test4;

import java.util.List;

/**
 * @author zhouyanxiang
 * @Date 2021-04-2021/4/5-17:36
 */
public class Solution {
    int len, row, col;
    List<List<String>> m;
    int[][] fs = new int[][]{{-1, 0}, {1, 0}, {0, 1}, {0, -1}, {0, 0}};
    int xP, yP;
    Boolean[][][][][] memo;

    public boolean escapeMaze(List<List<String>> maze) {
        len = maze.size();
        row = maze.get(0).size();
        col = maze.get(0).get(0).length();
        m = maze;
        memo = new Boolean[len][row][col][2][2];
        return dfs(0, 0, 0, 0, 0);
    }

    private boolean dfs(int u, int i, int j, int use1, int use2) {
        if (i == row - 1 && j == col - 1) {
            return true;
        }
        if (u == len - 1) {
            return false;
        }
        if (memo[u][i][j][use1][use2] != null) {
            return memo[u][i][j][use1][use2];
        }
        for (int[] f : fs) {
            int x = i + f[0];
            int y = j + f[1];
            if (x >= 0 && x < row && y >= 0 && y < col) {
                if (m.get(u + 1).get(x).charAt(y) == '.' || x == xP && y == yP) {
                    if (dfs(u + 1, x, y, use1, use2)) {
                        return memo[u][i][j][use1][use2] = true;
                    }
                } else {
                    if (use1 == 0) {
                        if (dfs(u + 1, x, y, 1, use2)) {
                            return memo[u][i][j][use1][use2] = true;
                        }
                    }
                    if (use2 == 0) {
                        xP = x;
                        yP = y;
                        if (dfs(u + 1, x, y, use1, 1)) {
                            return memo[u][i][j][use1][use2] = true;
                        }
                    }
                }
            }
        }
        return memo[u][i][j][use1][use2] = false;
    }
}
